home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / c / tagsgen.exe / MATCH.C < prev    next >
C/C++ Source or Header  |  1992-01-06  |  19KB  |  579 lines
  1. /*
  2.  EPSHeader
  3.  
  4.    File: match.c
  5.    Author: J. Kercheval
  6.    Created: Sat, 01/05/1991  22:21:49
  7. */
  8.  
  9. /*
  10.  EPSRevision History
  11.  
  12.    J. Kercheval  Wed, 02/20/1991  22:29:01  Released to Public Domain
  13.    J. Kercheval  Fri, 02/22/1991  15:29:01  fix '\' bugs (two :( of them)
  14.    J. Kercheval  Sun, 03/10/1991  19:31:29  add error return to matche()
  15.    J. Kercheval  Sun, 03/10/1991  20:11:11  add is_valid_pattern code
  16.    J. Kercheval  Sun, 03/10/1991  20:37:11  beef up main()
  17.    J. Kercheval  Tue, 03/12/1991  22:25:10  Released as V1.1 to Public Domain
  18.    J. Kercheval  Thu, 03/14/1991  22:22:25  remove '\' for DOS file parsing
  19.    J. Kercheval  Mon, 05/13/1991  21:49:05  ifdef full match code
  20.    J. Kercheval  Mon, 01/06/1992  21:31:44  add match character defines
  21. */
  22.  
  23. /*
  24.  * Wildcard Pattern Matching
  25.  */
  26.  
  27.  
  28. #include "match.h"
  29.  
  30. /* character defines */
  31. #define MATCH_CHAR_SINGLE               '?'
  32. #define MATCH_CHAR_KLEENE_CLOSURE       '*'
  33. #define MATCH_CHAR_RANGE_OPEN           '['
  34. #define MATCH_CHAR_RANGE                '-'
  35. #define MATCH_CHAR_RANGE_CLOSE          ']'
  36. #define MATCH_CHAR_LITERAL              '\\'
  37. #define MATCH_CHAR_NULL                 '\0'
  38. #define MATCH_CHAR_CARAT_NEGATE         '^'
  39. #define MATCH_CHAR_EXCLAMATION_NEGATE   '!'
  40.  
  41. /* forward function prototypes */
  42. int matche_after_star(register char *pattern, register char *text);
  43. int fast_match_after_star(register char *pattern, register char *text);
  44.  
  45.  
  46. /*----------------------------------------------------------------------------
  47.  *
  48.  * Return TRUE if PATTERN has any special wildcard characters
  49.  *
  50.  ---------------------------------------------------------------------------*/
  51.  
  52. BOOLEAN is_pattern(char *p)
  53. {
  54.     while (*p) {
  55.         switch (*p++) {
  56.                 case MATCH_CHAR_SINGLE:
  57.                 case MATCH_CHAR_KLEENE_CLOSURE:
  58.                 case MATCH_CHAR_RANGE_OPEN:
  59.  
  60. #ifndef FILE_MATCH
  61.                 case MATCH_CHAR_LITERAL:
  62. #endif
  63.  
  64.                 return TRUE;
  65.         }
  66.     }
  67.     return FALSE;
  68. }
  69.  
  70.  
  71. /*----------------------------------------------------------------------------
  72.  *
  73.  * Return TRUE if PATTERN has is a well formed regular expression according
  74.  * to the above syntax
  75.  *
  76.  * error_type is a return code based on the type of pattern error.  Zero is
  77.  * returned in error_type if the pattern is a valid one.  error_type return
  78.  * values are as follows:
  79.  *
  80.  *   PATTERN_VALID - pattern is well formed
  81.  
  82. #ifndef FILE_MATCH
  83.  *   PATTERN_ESC   - pattern has invalid escape ('\' at end of pattern)
  84. #endif
  85.  
  86.  *   PATTERN_RANGE - [..] construct has a no end range in a '-' pair (ie [a-])
  87.  *   PATTERN_CLOSE - [..] construct has no end bracket (ie [abc-g )
  88.  *   PATTERN_EMPTY - [..] construct is empty (ie [])
  89.  *
  90.  ---------------------------------------------------------------------------*/
  91.  
  92. BOOLEAN is_valid_pattern(char *p, int *error_type)
  93. {
  94.  
  95.     /* init error_type */
  96.     *error_type = PATTERN_VALID;
  97.  
  98.     /* loop through pattern to EOS */
  99.     while (*p) {
  100.  
  101.         /* determine pattern type */
  102.         switch (*p) {
  103.  
  104. #ifndef FILE_MATCH
  105.                 /* check literal escape, it cannot be at end of pattern */
  106.             case MATCH_CHAR_LITERAL:
  107.                 if (!*++p) {
  108.                     *error_type = PATTERN_ESC;
  109.                     return FALSE;
  110.                 }
  111.                 p++;
  112.                 break;
  113. #endif
  114.  
  115.                 /* the [..] construct must be well formed */
  116.             case MATCH_CHAR_RANGE_OPEN:
  117.                 p++;
  118.  
  119.                 /* if the next character is ']' then bad pattern */
  120.                 if (*p == MATCH_CHAR_RANGE_CLOSE) {
  121.                     *error_type = PATTERN_EMPTY;
  122.                     return FALSE;
  123.                 }
  124.  
  125.                 /* if end of pattern here then bad pattern */
  126.                 if (!*p) {
  127.                     *error_type = PATTERN_CLOSE;
  128.                     return FALSE;
  129.                 }
  130.  
  131.                 /* loop to end of [..] construct */
  132.                 while (*p != MATCH_CHAR_RANGE_CLOSE) {
  133.  
  134.                     /* check for literal escape */
  135.                     if (*p == MATCH_CHAR_LITERAL) {
  136.                         p++;
  137.  
  138.                         /* if end of pattern here then bad pattern */
  139.                         if (!*p++) {
  140.                             *error_type = PATTERN_ESC;
  141.                             return FALSE;
  142.                         }
  143.                     }
  144.                     else
  145.                         p++;
  146.  
  147.                     /* if end of pattern here then bad pattern */
  148.                     if (!*p) {
  149.                         *error_type = PATTERN_CLOSE;
  150.                         return FALSE;
  151.                     }
  152.  
  153.                     /* if this a range */
  154.                     if (*p == MATCH_CHAR_RANGE) {
  155.  
  156.                         /* we must have an end of range */
  157.                         if (!*++p || *p == MATCH_CHAR_RANGE_CLOSE) {
  158.                             *error_type = PATTERN_RANGE;
  159.                             return FALSE;
  160.                         }
  161.                         else {
  162.  
  163.                             /* check for literal escape */
  164.                             if (*p == MATCH_CHAR_LITERAL)
  165.                                 p++;
  166.  
  167.                             /* if end of pattern here then bad pattern */
  168.                             if (!*p++) {
  169.                                 *error_type = PATTERN_ESC;
  170.                                 return FALSE;
  171.                             }
  172.                         }
  173.                     }
  174.                 }
  175.                 break;
  176.  
  177.                 /* all other characters are valid pattern elements */
  178.             case MATCH_CHAR_KLEENE_CLOSURE:
  179.             case MATCH_CHAR_SINGLE:
  180.             default:            /* "normal" character */
  181.                 p++;
  182.                 break;
  183.         }
  184.     }
  185.  
  186.     return TRUE;
  187. }
  188.  
  189.  
  190. /*----------------------------------------------------------------------------
  191.  *
  192.  * Match the pattern PATTERN against the string TEXT;
  193.  *
  194.  * returns MATCH_VALID if pattern matches, or an errorcode as follows
  195.  * otherwise:
  196.  *
  197.  *           MATCH_PATTERN  - bad pattern
  198.  
  199. #ifndef FILE_MATCH
  200.  *           MATCH_LITERAL  - match failure on literal mismatch
  201. #endif
  202.  
  203.  *           MATCH_RANGE    - match failure on [..] construct
  204.  *           MATCH_ABORT    - premature end of text string
  205.  *           MATCH_END      - premature end of pattern string
  206.  *           MATCH_VALID    - valid match
  207.  *
  208.  *
  209.  * A match means the entire string TEXT is used up in matching.
  210.  *
  211.  * In the pattern string:
  212.  *      `*' matches any sequence of characters (zero or more)
  213.  *      `?' matches any character
  214.  *      [SET] matches any character in the specified set,
  215.  *      [!SET] or [^SET] matches any character not in the specified set.
  216.  *      \ is allowed within a set to escape a character like ']' or '-'
  217.  *
  218.  * A set is composed of characters or ranges; a range looks like character
  219.  * hyphen character (as in 0-9 or A-Z).  [0-9a-zA-Z_] is the minimal set of
  220.  * characters allowed in the [..] pattern construct.  Other characters are
  221.  * allowed (ie. 8 bit characters) if your system will support them.
  222.  *
  223.  * To suppress the special syntactic significance of any of `[]*?!^-\', and
  224.  * match the character exactly, precede it with a `\'.
  225.  *
  226.  ---------------------------------------------------------------------------*/
  227.  
  228. int matche(register char *p, register char *t)
  229. {
  230.     register char range_start, range_end;       /* start and end in range */
  231.  
  232.     BOOLEAN invert;             /* is this [..] or [!..] */
  233.     BOOLEAN member_match;       /* have I matched the [..] construct? */
  234.     BOOLEAN loop;               /* should I terminate? */
  235.  
  236.     for (; *p; p++, t++) {
  237.  
  238.         /* if this is the end of the text then this is the end of the match */
  239.         if (!*t) {
  240.             return (*p == MATCH_CHAR_KLEENE_CLOSURE &&
  241.                     *++p == MATCH_CHAR_NULL) ?
  242.                 MATCH_VALID : MATCH_ABORT;
  243.         }
  244.  
  245.         /* determine and react to pattern type */
  246.         switch (*p) {